/*
package Algorithm.SortingAlgorithm;

import com.sun.org.apache.bcel.internal.generic.SWAP;
import com.sun.xml.internal.bind.v2.model.annotation.Quick;
import jdk.nashorn.internal.runtime.RewriteException;

*/
/**
 *
 *几种排序算法
 * @author long
 * @date 2020-03-14 17:57
 *//*

public class Sorting {




    //冒泡排序（升序）基本的排序算法
    //
    //拉勾教育版权所有：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=3
    public  static   int[]  BubbleSort(int[] sort){

        //判断每轮遍历中是否发生交换
        boolean isChange=true;
        //遍历开始，将isChange设置为false
        for (int i=0;i<sort.length-1&&isChange;i++){
            isChange=false;
            //进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生
           for (int j=0;j<sort.length-1-i;j++){
                if (sort[j]>sort[j+1]){
                    int temp=sort[j+1];
                    sort[j+1]=sort[j];
                    sort[j]=temp;
                    isChange=true;
                }
           }
        }
        return sort;
    }

    //基本的排序算法
    //
    //拉勾教育版权所有：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=3
    // 插入排序

    */
/**
     * 1.从第一个元素开始，该元素可以认为已经被排序；
     * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
     * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
     * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
     * 5.将新元素插入到该位置后；
     * 6.重复步骤2~5。
     * @param sort
     * @return
     *//*

    public static  int[] InsertionSort(int[] sort){
        //将数组的第一个元素当作已经排好序的，从第二个元素，即 i 从 1 开始遍历数组
        for (int i=1,j,current;i<sort.length;i++){
            //外围循环开始，把当前i指向的值用 current 保存
            current=sort[i];
            //指针j内循环，和current值比较，若 j所指向的值比current值大，则该数右移一位。
            for (j=i-1;j>=0&&sort[j]>current;j--){
                sort[j+1]=sort[j];
            }
            //内循环结束,j+1 所指向的位置就是 current 值插入的位置。
            sort[j+1]=current;

        }
        return sort;

    }

    */
/**归并排序
     核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，
     然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。
     归并排序将分治的思想体现得淋漓尽致。
     实现
     一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
     排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，
     不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
     * 常考的排序算法 lo第一个元素下表 hi 最有一个元素下标
     *//*

    public static  int [] MergeSort(int[] A, int lo, int hi){
        // 判断是否只剩下最后一个元素
        if (lo>=hi) return A;
        // 从中间将数组分成两个部分
        int mid=lo+(hi-lo)/2;
        // 分别递归地将左右两半排好序
        MergeSort(A,lo,mid);//左
        MergeSort(A,mid+1,hi);//右
         // 复制一份原来的数组
        int [] copy=A.clone();
        // 定义一个 k 指针表示从什么位置开始修改原来的数组，i 指针表示左半边的起始位置，j 表示右半边的起始位置
        int k=lo,i=lo,j=mid+1;
        // 将排好序的左右两半合并
        while (k<=hi){
            if (i>mid){//左半边的数都处理完毕，只剩下右半边的数，只需要将右半边的数逐个拷贝过去。
                A[k++]=copy[j++];
            }else if (j>hi){//右半边的数都处理完毕，只剩下左半边的数，只需要将左半边的数逐个拷贝过去就好。
                A[k++]=copy[i++];
            }else if (copy[j]<copy[i]){//右边的数小于左边的数，将右边的数拷贝到合适的位置，j 指针往前移动一位。
                A[k++]=copy[j++];
            }else {//左边的数小于右边的数，将左边的数拷贝到合适的位置，i 指针往前移动一位。
                A[k++]=copy[i++];
            }
        }
        return A;
    }

    */
/**
     * 快速排序也采用了分治的思想。
     *实现
     把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
     举例：把班里的所有同学按照高矮顺序排成一排。
     * @return
     *//*

    public static  int[] QuickSort(int[] nums,int lo,int hi){
        if (lo>=hi) return nums; //判断是否只剩下一个元素，是，则直接返回.

        //利用partition 函数找到一个随机的基准点
        int p=partition(nums,lo,hi);

        //递归的对基准点左半边和右半边的数进行排序。
        QuickSort(nums,lo,p-1);
        QuickSort(nums,p+1,hi);
        return nums;
    }

    */
/**
     * 获得基准值函数
     * @param nums
     * @param lo
     * @param hi
     * @return
     *//*

    public int partition(int[] nums,int lo,int hi){
        //随机选择一个数作为基准值，nums[hi] 就是基准值
        swap(nums,randRange(lo,hi),hi);
        int i,j;
    // 从左到右用每个数和基准值比较，若比基准值小，则放到指针 i 所指向的位置。循环完毕后，i 指针之前的数都比基准值小
        for (i=lo,j=lo;j<hi;j++){
            if (nums[j]<=nums[hi]){
                swap(nums,i++,j);
            }
        }
    // 末尾的基准值放置到指针 i 的位置，i 指针之后的数都比基准值大
        swap(nums,i,j);
    // 返回指针 i，作为基准点的位置
        return i;
    }

    public void swap(int[] nums,int i,int j){

    }



    public static void main(String[] args) {
        int arr[] = {8, 5, 3, 2, 4,6,1};
        int[] ints = MergeSort(arr,0,6);



        for (int i=0;i<ints.length;i++){
            System.out.println(ints[i]);
        }

    }



}
*/
